package leetcode.hot100;

import leetcode.common.ListNode;

@SuppressWarnings("all")
public class _141_环形链表 {

    // 给定一个链表，判断链表中是否有环
    // 用 O(1)（即，常量）内存解决此问题
    public boolean hasCycle(ListNode head) {
        if (head == null) return false;
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;
        ListNode fast = dummyNode;
        ListNode slow = dummyNode;
        // 快指针走两步，慢指针走一步，如果有环，那么快指针一定会追上慢指针
        // 可以把环形指针看作一个足球跑道
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }
}
